{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Lecture 6: Combinatorics\n",
    "**References:**\n",
    "* [Introduction to combinatorics in SageMath](https://doc.sagemath.org/html/en/reference/combinat/sage/combinat/tutorial.html)\n",
    "* [List of combinatorial functions in SageMath](https://doc.sagemath.org/html/en/reference/combinat/sage/combinat/combinat.html#sage-combinat-combinat)\n",
    "\n",
    "**Summary:**<br>\n",
    "We start by recalling the Python datatype of **sets** and showing a nice trick for finding **extreme values** of functions on a finite set. Then we discuss useful functions in combinatorics, including **cartesian products**, how to enumerate **subsets**, **partitions** and various types of **integer vectors**. We also show how to use the **online encyclopedia of integer sequences** to identify interesting sequences of numbers."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Python warmup: sets\n",
    "One of the basic data types in Python are *sets*, which are unordered collections of objects."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "S = {7,3,5,2}\n",
    "S"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we list an element multiple times, it is still only recorded once in the set:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "T = {2,4,2}\n",
    "T"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can form unions, intersections and relative complements of sets:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "S.union(T)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "S.intersection(T)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "S-T"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "An important way to create sets is to obtain them by converting a list (or tuple) into a set:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "W = set([sin(pi*t/2) for t in range(100)])\n",
    "W"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Exercise\n",
    "* Create the set $E$ of all even numbers $4, \\ldots, 100$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Create the set $P$ of all primes between $2$ and $100$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Check the Goldbach conjecture (\"Every even number $n$ greater than $2$ is the sum of two primes\") for $n \\leq 100$.<br>\n",
    "*Hint:* If only there was a *method* to check whether a set is a subset of another set."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Solution** (uncomment to see)\n",
    "<!---\n",
    "```\n",
    "E = set(range(4,102,2))\n",
    "P = set(primes(2,100))\n",
    "P2 = set([p1 + p2 for p1 in P for p2 in P])\n",
    "E.issubset(P2)\n",
    "> True\n",
    "```\n",
    "--->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "One final word of warning: elements of a set must be *hashable*. Here a [*hash*](https://docs.python.org/2/library/functions.html#hash) is an integer assigned to a Python object, only depending on its value, so that (hopefully) two objects are equal only if their hashes are equal. An example of an unhashable type are lists, which is why the following does not work:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "{[1,2],[3,4]}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This could be repaired by using a *tuple*, i.e. a list that cannot be changed:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "{(1,2),(3,4)}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Python warmup: finding extreme values\n",
    "In one exercise below (but also more generally) we encounter the following situation: we have list (or set) ``L`` and a function ``f`` from ``L`` to the real numbers, and want to find an element ``l`` such that ``f(l)`` is minimal (or maximal). The following is a nice trick to find such an element:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "L = [(p,q) for p in range(20) for q in range(1,20)]\n",
    "f = lambda x,y : abs(pi - x / y)  # the function (x,y) -> |pi - x/y|\n",
    "min((f(p,q), p, q) for p, q in L)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This uses that when ordering tuples (such as ``(f(p,q), p, q)``) and finding the minimum, Python will first sort by the *first* entry, and only for equal first entries start sorting by the second entry etc. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Exercise\n",
    "For which integer $a \\in \\{0, \\ldots, 100\\}$ is the value $\\sin(a)$ maximal? What is the value for this $a$ (approximately)?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Solution** (uncomment to see)<br>\n",
    "<!---\n",
    "```\n",
    "L = list(range(101))\n",
    "f =  lambda a: sin(a)\n",
    "max((f(a), a) for a in L)\n",
    "> (sin(33), 33)\n",
    "n(sin(33))\n",
    "> 0.999911860107267\n",
    "```\n",
    "--->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Combinatorics\n",
    "Below we will see different ways of enumerating certain objects (such as partitions, integer vectors with given sums, permutations etc.). One very useful tool when studying combinatorics is the [On-line Encyclopedia of Integer Sequences](https://oeis.org/). This is a database of meaningful sequences of integers. The idea is: if you come across some sequence of numbers and wonder whether there is a pattern explaining them, you can look up this sequence in the OEIS database and check whether it appears somewhere."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "oeis([3,1,4,1,5])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "oeis('A000796')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "vector(oeis('A000796').first_terms())  # using vector to avoid long output"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Exercise\n",
    "What is the next element of the sequence\n",
    "```\n",
    "0, 1, 5, 14, 30, 55, 91, 140, 204, 285, 385, 506 ?\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Solution** (uncomment to see)\n",
    "<!---\n",
    "```\n",
    "oeis([0, 1, 5, 14, 30, 55, 91, 140, 204, 285, 385, 506])\n",
    "> 0: A000330: Square pyramidal numbers: a(n) = 0^2 + 1^2 + 2^2 + ... + n^2 = n*(n+1)*(2*n+1)/6.\n",
    "vector(oeis('A000330').first_terms())\n",
    "> (0, 1, 5, 14, 30, 55, 91, 140, 204, 285, 385, 506, 650, 819, 1015, 1240, 1496, 1785, 2109, 2470, 2870, 3311, 3795, 4324, 4900, 5525, 6201, 6930, 7714, 8555, 9455, 10416, 11440, 12529, 13685, 14910, 16206, 17575, 19019, 20540, 22140, 23821, 25585, 27434, 29370)\n",
    "```\n",
    "So the next element should be $650$.\n",
    "--->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Products\n",
    "A basic operation in enumerative combinatorics is the cartesian product of sets:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "C = {'red', 'blue', 'green'}\n",
    "N = {1,2,3,4}\n",
    "P = cartesian_product([C,N]); P"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "P.cardinality()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "list(P)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Instead of an exercise, let's just show a fun application:\n",
    "#### Question\n",
    "Can you insert operations ``+, *, -`` in the equation below such that it becomes true?\n",
    "```\n",
    "13 _ 9 _ 4 _ 6 _ 21 = 208\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "ops = {'+', '*', '-'}\n",
    "\n",
    "for o1, o2, o3, o4 in cartesian_product(4*[ops]):\n",
    "    st = '13'+o1+'9'+o2+'4'+o3+'6'+o4+'21'\n",
    "    if eval(st) == 208:\n",
    "        print(st+' = 208')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Subsets\n",
    "A second operation is forming the *power set* of $S$, i.e. the set of subsets of $S$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "S = {1,2,3,4}\n",
    "PS = Subsets(S); PS"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "PS.cardinality()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for s in PS:\n",
    "    print(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can also restrict to subsets of a given size:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "PS2 = Subsets(S,2); PS2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Exercise\n",
    "Consider the alternating group $A_4$ and let $S \\subseteq A_4$ be a subset of two different elements of $A_4$, chosen uniformly at random. Compute the probability\n",
    "$$\n",
    "\\mathbb{P}(S\\text{ generates }A_4).\n",
    "$$\n",
    "*Remark:* Considering more generally the group $A_n$, this probability tends to $1$ as $n \\to \\infty$, as proven by [Dixon](https://books.google.ch/books?id=wBPgJjZHXzsC&pg=PA164&redir_esc=y#v=onepage&q&f=false). Replacing $A_n$ by $S_n$, the probability tends to $3/4$. Can you see why it can't be greater than $3/4$?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Solution** (uncomment to see)\n",
    "<!---\n",
    "```\n",
    "G = AlternatingGroup(4)\n",
    "Sset = Subsets(G,2)\n",
    "sum(1 for A in Sset if G.subgroup(A) == G) / Sset.cardinality()\n",
    "```\n",
    "--->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Permutations\n",
    "Given $n \\geq 1$ we can list all permutations of the set $\\{1, \\ldots, n\\}$:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "P = Permutations(4); P"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "list(P)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can also look at permutations of any other set/list:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Q = Permutations([3,4,5])\n",
    "list(Q)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Exercise\n",
    "Consider the following two vectors:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "A = (2,5,7,12,34)\n",
    "B = (1,3,6,7,11)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For which permutation $\\sigma \\in S_5$ is the sum\n",
    "$$\n",
    "\\sum_{i=1}^5 A_i B_{\\sigma(i)}\n",
    "$$\n",
    "minimal?<br>\n",
    "*Optional:* Can you make a guess, even before computing the answer?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Solution** (uncomment to see)<br>\n",
    "<!---\n",
    "```\n",
    "L = list(Permutations(B))\n",
    "f = lambda Bperm : sum(A[i]*Bperm[i] for i in range(5))\n",
    "min((f(Bperm), Bperm) for Bperm in L)\n",
    "> (169, [11, 7, 6, 3, 1])\n",
    "```\n",
    "We see that we must precisely take the permutation of $B$ that sorts in in descending order. Intuitively, this is clear: big numbers in $A$ should be multiplied by small numbers in $B$. And indeed, this is a special case of the [rearrangement inequality](https://en.wikipedia.org/wiki/Rearrangement_inequality).\n",
    "--->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Partitions and integer vectors\n",
    "We have already seen that a *partition* of $n$ is a way to write $n$ as a sum of positive integers, regardless of orientation. We can enumerate these as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "P = Partitions(5)\n",
    "list(P)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There are also several optional arguments that can restrict the shape of the partition (see the documentation of ``Partitions`` for more details):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "list(Partitions(5, length=3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "list(Partitions(5, max_part=3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "list(Partitions(5, max_part=3, min_part=2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can also look at the related problem where the order of the summands matters. In other words, of enumerating vectors of integers summing to a given number. Here, since $0$ counts as an integer, we have to either restrict the length of the vector, or give some minimal part in order to obtain a finite set (otherwise we have $(n), (n,0), (n,0,0), \\ldots$ as solutions):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "I = IntegerVectors(5, length=3); I"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "list(I)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "list(IntegerVectors(6,min_part=2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Exercise\n",
    "A frog sits on the origin of the real axis and wants to hop to the number $n$. It always jumps in positive direction, and its jumps can either have length $1$ or length $2$. \n",
    "* Compute the number $J(n)$ of ways that the frog can jump from $0$ to $n$ for $n=1, \\ldots, 9$.\n",
    "* What is the number $J(n)$ in general? Can you see a proof?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Solution** (uncomment to see)<br>\n",
    "<!---\n",
    "A jumping pattern of the frog can be described by a vector of integers (with all entries being $1$ or $2$) which sums to $n$. Thus the following are the desired numbers $J(n)$:\n",
    "```\n",
    "[len(IntegerVectors(n, min_part = 1, max_part=2)) for n in range(10)]\n",
    "> [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]\n",
    "```\n",
    "Obviously, these are the Fibonacci numbers! If we didn't see it ourselves, we could of course have used the OEIS:\n",
    "```\n",
    "oeis([1, 1, 2, 3, 5, 8, 13, 21, 34, 55])\n",
    "> \n",
    "0: A000045: Fibonacci numbers: F(n) = F(n-1) + F(n-2) with F(0) = 0 and F(1) = 1.\n",
    "1: A290689: Number of transitive rooted trees with n nodes.\n",
    "2: A212804: Expansion of (1 - x)/(1 - x - x^2).\n",
    "```\n",
    "Showing the recursion $J(n) = J(n-1) + J(n-2)$ is not hard: a jumping pattern can either start with $1$ or with $2$, and then the remaining jumping pattern is either of length $n-1$ (for which we have $J(n-1)$ possibilities) or of length $n-2$ (for which we have $J(n-2)$ possibilities).\n",
    "--->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Set partitions\n",
    "Finally, we can enumerate all ways of writing a given set $S$ as a disjoint union of subsets:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "C = SetPartitions([1,2,3])\n",
    "list(C)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Exercise\n",
    "* Compute the numbers $B_n$ of set partitions of $\\{1, \\ldots, n\\}$ for $n=0, \\ldots, 9$. \n",
    "* Find out what the numbers $B_n$ are called.\n",
    "* The numbers $B_n$ have a nice *exponential generating series*:\n",
    "$$\n",
    "B(x) = \\sum_{n=0}^\\infty \\frac{B_n}{n!} x^n = e^{e^x -1}\\,.\n",
    "$$\n",
    "Use this formula to compute $B_{19}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Solution** (uncomment to see)<br>\n",
    "<!---\n",
    "```\n",
    "Bvec = [len(SetPartitions(range(n))) for n in range(10)]; Bvec\n",
    "> [1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147]\n",
    "oeis(Bvec)\n",
    ">\n",
    "0: A000110: Bell or exponential numbers: number of ways to partition a set of n labeled elements.\n",
    "1: A164864: Number of ways of placing n labeled balls into 10 indistinguishable boxes; word structures of length n using a 10-ary alphabet.\n",
    "2: A164863: Number of ways of placing n labeled balls into 9 indistinguishable boxes; word structures of length n using a 9-ary alphabet.\n",
    "```\n",
    "Indeed the numbers $B_n$ are called the *Bell numbers*. If you don't believe me about their generating series, maybe you believe the OEIS:\n",
    "```\n",
    "oeis('A000110').formulas()\n",
    ">\n",
    "0: E.g.f.: exp(exp(x) - 1).\n",
    " 1: Recurrence: a(n+1) = Sum_{k=0..n} a(k)*binomial(n, k).\n",
    " 2: a(n) = Sum_{k=0..n} Stirling2(n, k).\n",
    " 3: a(n) = Sum_{j=0..n-1} (1/(n-1)!)*A000166(j)*binomial(n-1, j)*(n-j)^(n-1). - _André F. Labossière_, Dec 01 2004\n",
    " ...\n",
    "```\n",
    "Here ``E.g.f.`` stands for exponential generating function. Using the power series rings that we saw in a previous lecture, it is not so hard to compute $B_{19}$:\n",
    "```\n",
    "R.<t> = PowerSeriesRing(QQ)\n",
    "f = exp(exp(t)-1)\n",
    "f[19] * factorial(19)\n",
    "> 5832742205057\n",
    "```\n",
    "--->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Exercise\n",
    "List all partitions \n",
    "$$\n",
    "\\{1, \\ldots, 10\\} = \\coprod_i S_i\n",
    "$$\n",
    "into disjoint subsets $S_i$ such that all $S_i$ have the same sum (e.g. in the smaller example $\\{1,2,3,4\\} = \\{1,4\\} \\cup \\{2,3\\}$ would be a solution, since $1+4=2+3$)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Solution** (uncomment to see)<br>\n",
    "<!---\n",
    "We list all set partitions $S$ and for a given partition\n",
    "$$\n",
    "\\{1, \\ldots, 10\\} = S_1 \\cup \\ldots \\cup S_\\ell,\n",
    "$$\n",
    "we simply compute the set\n",
    "$$\n",
    "\\Sigma = \\{\\sum_{s \\in S_i} s : i=1, \\ldots, \\ell\\}.\n",
    "$$\n",
    "Our set partition satisfies the condition of the exercise, if this set $\\Sigma$ has precisely one element.\n",
    "```\n",
    "S = SetPartitions(range(1,11))\n",
    "for setpart in S:\n",
    "    sumset = set(sum(si) for si in setpart)\n",
    "    if len(sumset) == 1:\n",
    "        print(setpart)\n",
    "> \n",
    "{{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}}\n",
    "{{1, 10}, {2, 9}, {3, 8}, {4, 7}, {5, 6}}\n",
    "```\n",
    "So there are precisely two possibilities.\n",
    "--->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Appendix: sorting in Python\n",
    "For some computations it can be useful to sort elements in a list. This comes in two variants: firstly, we can create a new list, which is the sorted version of the old one:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "L = [5,2,3,1,2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sorted(L)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This doesn't change the list itself:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "L"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can also *change* the original list by sorting it:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "L.sort()\n",
    "L"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can also sort in the opposite direction:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sorted(L, reverse=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And finally, we can specify a ``key`` function ourselves. This is a function which sends the elements of our list to numbers, and the list is then sorted in increasing order of these numbers:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "L = [(1,0), (0,2), (4,-1)]\n",
    "sorted(L, key = lambda v : v[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sorted(L, key = lambda v : v[0]+v[1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here we used the a ``lambda``-function, which is a short way to define a function. For example, the following two constructions define the same functions:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "f1 = lambda a,b : a+b\n",
    "\n",
    "def f2(a,b):\n",
    "    return a+b"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If this was a *very* serious lecture on computer algebra, I could discuss some [sorting algorithms](https://en.wikipedia.org/wiki/Sorting_algorithm) and how they allow to sort a list with $n$ elements using $O(n \\log(n))$ operations. But it's not, and so we won't."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Assignments"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Exercise\n",
    "* Compute the number of conjugacy classes of $S_n$ for $n=1, \\ldots, 6$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Do you know (or can you find out) what this sequence of integers is?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Solution** (uncomment to see)\n",
    "<!---\n",
    "```\n",
    "[len(SymmetricGroup(n).conjugacy_classes()) for n in range(11)]\n",
    "> [1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42]\n",
    "```\n",
    "Using the online encyclopedia of integer sequences, we can identify these numbers:\n",
    "```\n",
    "oeis([1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42])\n",
    "> \n",
    "0: A000041: a(n) is the number of partitions of n (the partition numbers).\n",
    "1: A026816: Number of partitions of n in which the greatest part is 10.\n",
    "2: A194439: Number of regions in the set of partitions of n that contain only one part.\n",
    "```\n",
    "And indeed, the [number of conjugacy classes of the symmetric group](https://en.wikipedia.org/wiki/Symmetric_group#Conjugacy_classes) equals the partition number, since a conjugacy class is uniquely determined by its cycle type.\n",
    "--->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Exercise\n",
    "Recall the following question we saw above:\n",
    "> Can you insert operations ``+, *, -`` in the equation below such that it becomes true?\n",
    "```\n",
    "13 _ 9 _ 4 _ 6 _ 21 = 208\n",
    "```\n",
    "\n",
    "Write a function taking a list ``L`` (like ``[13,9,4,6,21]``) and an integer ``s`` (like ``208``) which prints out all possibilities of combining the elements of ``L`` using ``+,*,-`` and obtaining the number ``s``.<br>\n",
    "*Hint:* Some useful functions:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "''.join(['Hello', ' wor', 'ld'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "repr(12)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Solution** (uncomment to see)\n",
    "<!---\n",
    "```\n",
    "def combine(L, s):\n",
    "    ops = {'+', '*', '-'}\n",
    "    n = len(L)\n",
    "    for o in cartesian_product((n-1)*[ops]):\n",
    "        st = ''.join([repr(a)+u for a,u in zip(L[:-1], o)]) + repr(L[n-1])\n",
    "        if eval(st) == s:\n",
    "            print(st+' = '+repr(s))\n",
    "combine([13,9,4,6,21], 208)\n",
    "> 13+9*4*6-21 = 208\n",
    "```\n",
    "--->"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 9.1",
   "language": "sage",
   "name": "sagemath"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}